package sword.chapter4LinkList;

import leetcode.t4LinkedList.ListNode;

/**
 * 链表中的数字相加
 * 1. 翻转链表
 * 2. 链表相加，记录carry
 *
 * @author K
 * @date 2021/11/26 09:16
 */
public class S25AddTwoNumbers {
    public static void main(String[] args) {
        ListNode nodeA = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode nodeB = new ListNode(9);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        nodeA.next = node2;
        node2.next = node3;
        nodeB.next = node5;
        node5.next = node6;
        ListNode result = s25(nodeA, nodeB);
        System.out.println();
    }

    public static ListNode s25(ListNode a, ListNode b) {
        ListNode headA = reverseList(a);
        ListNode headB = reverseList(b);

        int carry = 0;
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        while (headA != null || headB != null) {
            int va = headA != null ? headA.val : 0;
            int vb = headB != null ? headB.val : 0;
            int sum = va + vb + carry;
            node.next = (new ListNode(sum % 10));
            carry = sum >= 10 ? 1 : 0;
            node = node.next;
            if (headA != null) {
                headA = headA.next;
            }
            if (headB != null) {
                headB = headB.next;
            }
        }
        if (carry == 1) {
            node.next = (new ListNode(1));
        }

        return reverseList(dummy.next);
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = (pre);
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
